package com.example.base;

/**
 * Author: liaohailong
 * Time: 2021/11/25 11:33
 * Describe: 排序
 */
public class SortStudy {

    // 快速排序
    public static void quick(int[] arr) {
        _quick(arr, 0, arr.length - 1);
    }

    private static void _quick(int[] arr, int low, int high) {
        if (low >= high) return;
        // 分拣法
        int mid = _partition(arr, low, high);
        _quick(arr, low, mid - 1);
        _quick(arr, mid + 1, high);
    }

    private static int _partition(int[] arr, int low, int high) {
        // 取出第一个
        int temp = arr[low];

        while (low < high) {
            while (arr[high] >= temp && low < high) high--;
            if (low < high) {
                arr[low] = arr[high];
                low++;
            }
            while (arr[low] < temp && low < high) low++;
            if (low < high) {
                arr[high] = arr[low];
                high--;
            }
        }

        // 此时low == high
        arr[low] = temp;

        return low;
    }


    // 选择排序，先确定最小的在左边
    public static void selection(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            for (int k = i + 1; k < N; k++) {
                if (arr[i] > arr[k]) {
                    int temp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = temp;
                }
            }
        }
    }

    // 冒泡排序，先确定最大的在右边
    public static void bubble(int[] arr) {
        int N = arr.length;
        for (int i = 0; i < N; i++) {
            for (int j = 1; j < N - i; j++) {
                if (arr[j - 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }

    // 插入排序，提值比较，移动数组
    public static void insertion(int[] arr) {
        if (arr.length < 2) return;
        int N = arr.length;

        // 把待插入值提取出来
        int p = 1;
        int temp;
        while (p < N) {
            temp = arr[p];
            int insert = p;
            // 往左寻找插入位置，比arr[p]大的值都右移动，直到找到比arr[p]小的值
            for (int i = p - 1; i >= 0; i--) {
                if (arr[i] >= temp) {
                    // i位置元素后移
                    arr[i + 1] = arr[i];
                    insert = i;
                } else break;
            }
            // 找到插入位置
            arr[insert] = temp;
            p++;
        }
    }

    /**
     * 1，二分法，化整为零
     * 2，合并两个有序集合
     * <p>
     * 与快排比较：
     * 优点： 稳定的时间复杂度，快速排序的时间复杂度不够稳定
     * 缺点：空间复杂度O(n)，快排是O(1)
     *
     * @param arr 归并排序，时间复杂度：O(nlogN) 空间复杂度：O(n)
     */
    public static void merge(int[] arr) {
        int[] temp = new int[arr.length];
        _mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void _mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;

            // 二分法拆分范围，左闭右开
            _mergeSort(arr, left, mid, temp);
            _mergeSort(arr, mid + 1, right, temp);

            // 合并两个有序集合
            _merge(arr, left, mid, right, temp);
        }
    }

    private static void _merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid || j <= right) {
            // 左右集合都有数据
            if (i <= mid && j <= right) {
                if (arr[i] == arr[j]) {
                    // 两个一起合并
                    temp[k++] = arr[i++];
                    temp[k++] = arr[j++];
                } else if (arr[i] < arr[j]) {
                    // 左集合取数据
                    temp[k++] = arr[i++];
                } else if (arr[i] > arr[j]) {
                    // 右集合取数据
                    temp[k++] = arr[j++];
                }
            } else if (i <= mid) {
                // 左集合还有数据，右集合没数据
                temp[k++] = arr[i++];
            } else if (j <= right) {
                // 右集合还有数据，左集合没数据
                temp[k++] = arr[j++];
            }
        }
        // 放入原数组
        for (int p = 0; p < k; p++) {
            arr[left++] = temp[p];
        }
    }


    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j]; // 把i位置的值，放在j上
        arr[i] = arr[i] ^ arr[j]; // j位置上现在是i的值，异或得出j值，放到i上
    }
}
